/*
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
*/

//基于快速排序的选择方法
class Solution
{
public:
    int quickSelect(vector<int> &a, int l, int r, int index)
    {
        int q = randomPartition(a, l, r);
        if (q == index)
        {
            return a[q];
        }
        else
        {
            return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
        }
    }

    //打乱
    inline int randomPartition(vector<int> &a, int l, int r)
    {
        int i = rand() % (r - l + 1) + l;
        swap(a[i], a[r]);
        return partition(a, l, r);
    }

    inline int partition(vector<int> &a, int l, int r)
    {
        int x = a[r], i = l - 1;
        for (int j = l; j < r; ++j)
        {
            if (a[j] <= x)
            {
                swap(a[++i], a[j]);
            }
        }
        swap(a[i + 1], a[r]);
        return i + 1;
    }

    int findKthLargest(vector<int> &nums, int k)
    {
        srand(time(0));
        return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
    }
};





//基于堆排序的选择方法
class Solution
{
public:
    void maxHeapify(vector<int> &a, int i, int heapSize)
    {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest])
        {
            largest = l;
        }
        if (r < heapSize && a[r] > a[largest])
        {
            largest = r;
        }
        if (largest != i)
        {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int> &a, int heapSize)
    {
        for (int i = heapSize / 2; i >= 0; --i)
        {
            maxHeapify(a, i, heapSize);
        }
    }

    int findKthLargest(vector<int> &nums, int k)
    {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i)
        {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};

//215 数组中的第K大元素
//省略打乱的步骤，
// 主函数
int findKthLargest(vector<int> &nums, int k)
{
    //target
    int l = 0, r = nums.size() - 1, target = nums.size() - k;
    while (l < r)
    {
        int mid = quickSelection(nums, l, r); //
        if (mid == target)
        {
            return nums[mid];
        }
        if (mid < target)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return nums[l];
}
// 辅函数 - 快速选择
int quickSelection(vector<int> &nums, int l, int r)
{
    int i = l + 1, j = r;
    while (true)
    {
        while (i < r && nums[i] <= nums[l])
        {
            ++i;
        }
        while (l < j && nums[j] >= nums[l])
        {
            --j;
        }
        if (i >= j)
        {
            break;
        }
        swap(nums[i], nums[j]);
    }
    swap(nums[l], nums[j]);
    return j;
}